package jmine.tec.utils.collection.impl;

import java.io.Serializable;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Set;

/**
 * {@link Set} implementation, intended to be used with small sets, resolving colisions by linear probing.
 * 
 * @author takeshi
 * @param <E> the type of the set
 */
public class SmallSet<E> extends AbstractSet<E> implements Set<E>, Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = -7445860917984987542L;

    private Object[] container;

    private double loadFactor;

    private int size;

    private final int initialSize;

    public static final int INITIAL_SIZE = 10;

    public static final double DEFAULT_LOAD_FACTOR = 0.75;

    public static final double DEFAULT_SHRINK_THRESHOLD = 0.1;

    private static final Object EMPTY = new Object();

    private volatile int modCount;

    private double shrinkThreshold = DEFAULT_SHRINK_THRESHOLD;

    /**
     * C'tor
     * 
     * @param capacity the initial capacity
     * @param loadFactor the load factor
     */
    public SmallSet(final int capacity, final double loadFactor) {
        this.initialSize = capacity;
        this.createContainer(capacity);
        this.loadFactor = loadFactor;
    }

    /**
     * @param capacity int the initial capacity
     */
    public SmallSet(final int capacity) {
        this(capacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * C'tor
     */
    public SmallSet() {
        this(INITIAL_SIZE, DEFAULT_LOAD_FACTOR);
    }

    /**
     * C'tor
     * 
     * @param col {@link Collection}
     */
    public SmallSet(final Collection<? extends E> col) {
        this();
        this.ensureCapacity(col.size());
        this.addAll(col);
    }

    /**
     * C'tor
     * 
     * @param es the Es
     */
    public SmallSet(final E... es) {
        this.initialSize = es.length;
        this.ensureCapacity(es.length);
        for (E e : es) {
            this.add(e);
        }
    }

    /**
     * @param capacity the capacity
     */
    private void createContainer(final int capacity) {
        this.container = new Object[capacity];
        for (int i = 0; i < this.container.length; i++) {
            this.container[i] = EMPTY;
        }
    }

    /**
     * @return double
     */
    protected double currentLoad() {
        return (double) this.size / (double) this.container.length;
    }

    /**
     * @param obj Object to probe index
     * @return int
     */
    protected int indexFor(final Object obj) {
        if (obj == null) {
            return 0;
        }
        final int val = obj.hashCode();
        return this.maskHash(val);
    }

    /**
     * Masks the given value to be contained within the boundaries of the container.
     * 
     * @param val int
     * @return int
     */
    private int maskHash(final int val) {
        return (val & Integer.MAX_VALUE) % this.container.length;
    }

    /**
     * @param value int
     * @return int
     */
    private int modSize(final int value) {
        int c = this.getCapacity();
        int v = value % c;
        if (v < 0) {
            v += c;
        }
        return v;
    }

    /**
     * Increases the capacity for this container by a factor of 2 plus 1. While this does not ensure primality of the container size, its a
     * very fast way of not getting an even number.
     */
    protected void increaseCapacity() {
        final int newSize = this.container.length * 2 + 1;
        // doubles + 1 the size
        this.changeContainerCapacity(newSize);
    }

    /**
     * increases capacity
     * 
     * @param newSize int
     */
    @SuppressWarnings("unchecked")
    private void changeContainerCapacity(final int newSize) {
        // subsequent calls should not alter
        if (this.container.length != newSize) {
            Object[] oldVals = this.container;
            this.createContainer(newSize);
            this.size = 0;
            for (Object object : oldVals) {
                if (object != EMPTY) {
                    this.add((E) object);
                }
            }
        }
    }

    /**
     * Ensures that at least the given number of objects might be held by this {@link Set}, without increasing its capacity.
     * 
     * @param newCapacity int
     */
    public void ensureCapacity(final int newCapacity) {
        if (this.getCapacity() >= newCapacity) {
            return;
        }
        int newSize = (int) Math.max(1.0, Math.ceil(newCapacity / this.loadFactor));
        this.changeContainerCapacity(newSize);
    }

    /**
     * Get the current capacity of this container.
     * 
     * @return int
     */
    public int getCapacity() {
        return this.container.length;
    }

    /**
     * Check the current load of this collection and increse its capacity if its greater than the defined load factor.
     */
    protected void checkLoadIncrease() {
        if (this.currentLoad() > this.loadFactor) {
            this.increaseCapacity();
        }
    }

    /**
     * @param o E to add
     * @return boolean true if this collection was modified in any matter
     */
    @Override
    public boolean add(final E o) {
        this.modCount++;
        int index = this.indexFor(o);
        int cap = this.container.length;
        int bound = this.modSize(index - 1);
        for (int i = index; i != bound; i = (i + 1) % cap) {
            if (this.container[i] == EMPTY) {
                this.container[i] = o;
                this.size++;
                this.checkLoadIncrease();
                return true;
                // add here
            } else if (equals(o, this.container[index])) {
                return false;
            }
        }
        // table is full. Maybe load factor is too high?
        this.ensureCapacity(this.getCapacity() + 1);
        return this.add(o);
    }

    /**
     * Compares two objects for {@link Object#equals(Object)} equality or if they are both null.
     * 
     * @param o {@link Object}
     * @param object {@link Object}
     * @return boolean
     */
    private static boolean equals(final Object o, final Object object) {
        if (o == null) {
            return object == null;
        } else {
            return o.equals(object);
        }
    }

    /**
     * 
     */
    @Override
    public void clear() {
        boolean mod = false;
        for (int i = 0; i < this.container.length; i++) {
            if (this.container[i] != EMPTY) {
                this.container[i] = EMPTY;
                this.size--;
                this.modCount++;
            }
        }
        if (mod) {

            this.checkLoadShrink();
        }
    }

    /**
     * @param o the Object to find.
     * @return int index in the table
     */
    protected int findObject(final Object o) {
        int index = this.indexFor(o);
        int cap = this.getCapacity();
        // int bound = (index - 1) % cap;
        int bound = this.modSize(index - 1);
        for (int i = index; i != bound; i = (i + 1) % cap) {
            if (this.container[i] == EMPTY) {
                return -1;
            }
            if (equals(o, this.container[i])) {
                return i;
            }
        }
        if (equals(o, this.container[bound])) {
            return bound;
        }
        return -1;
    }

    /**
     * Check if the given index is within this container's bound.
     * 
     * @param index index
     * @return boolean
     */
    protected boolean checkBounds(final int index) {
        return (index >= 0) && (index < this.getCapacity());
    }

    /**
     * Removes the given object from this Set.
     * 
     * @param o Object to remove
     * @return <code>true</code> if the object was previously on this set.
     */
    @Override
    public boolean remove(final Object o) {
        int index = this.findObject(o);
        if (this.removeAt(index)) {
            this.checkLoadShrink();
            return true;
        }
        return false;
    }

    /**
     * Removes the object at the given index
     * 
     * @param index int
     * @return boolean
     */
    private boolean removeAt(final int index) {
        if (this.checkBounds(index)) {
            this.modCount++;
            this.container[index] = EMPTY;
            this.size--;
            return true;
        }
        return false;
    }

    /**
     * @param c {@link Collection}
     * @return boolean
     */
    @Override
    public boolean removeAll(final Collection<?> c) {
        if (c == this) {
            if (this.isEmpty()) {
                return false;
            }
            this.clear();
            return true;
        }
        boolean mod = false;
        for (Object object : c) {
            int index = this.findObject(object);
            if (this.checkBounds(index)) {
                mod = true;
                this.modCount++;
                this.container[index] = EMPTY;
                this.size--;
            }
        }
        if (mod) {
            this.checkLoadShrink();
            return true;
        }
        return false;
    }

    /**
     * 
     * 
     */
    private void checkLoadShrink() {
        if (this.currentLoad() < this.shrinkThreshold && this.getCapacity() >= this.initialSize) {
            int newSize = (int) Math.max(this.getCapacity() * this.shrinkThreshold, this.size / this.loadFactor) + 1;
            this.changeContainerCapacity(Math.max(newSize, this.initialSize));
            // fallback at least to the size set on construction
        }
    }

    /**
     * @param c {@link Collection} to retain
     * @return boolean
     */
    @SuppressWarnings("unchecked")
    @Override
    public boolean retainAll(final Collection<?> c) {
        Collection<Object> toUse;
        if (!(c instanceof Set)) {
            toUse = new SmallSet<Object>(c);
        } else {
            toUse = (Collection<Object>) c;
        }
        boolean mod = false;
        for (int i = 0; i < this.container.length; i++) {
            Object obj = this.container[i];
            if ((obj != EMPTY) && !toUse.contains(obj)) {
                mod = this.removeAt(i);
            }
        }
        return mod;
    }

    /**
     * @param c Collection to add;
     * @return if this collection was modified
     */
    @Override
    public boolean addAll(final Collection<? extends E> c) {
        this.ensureCapacity(c.size() + this.size);
        return super.addAll(c);
    }

    /**
     * @return {@link Iterator}
     */
    @Override
    public Iterator<E> iterator() {
        return new SkipEmptyIterator();
    }

    /**
     * @return int
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * @param o Object to probe
     * @return boolean
     */
    @Override
    public boolean contains(final Object o) {
        return this.findObject(o) >= 0;
    }

    /**
     * @param c {@link Collection}
     * @return boolean
     */
    @Override
    public boolean containsAll(final Collection<?> c) {
        for (Object object : c) {
            if (!this.contains(object)) {
                return false;
            }
        }
        return true;
    }

    /**
     * @author takeshi
     */
    private class SkipEmptyIterator implements Iterator<E> {
        private int index = 0;

        private int expectedModCount = SmallSet.this.modCount;

        /**
         * @return boolean
         */
        public boolean hasNext() {
            this.checkModCount();
            for (; this.index < SmallSet.this.getCapacity(); this.index++) {
                if (SmallSet.this.container[this.index] != EMPTY) {
                    return true;
                }
            }
            return false;
        }

        /**
         * @return E
         */
        @SuppressWarnings("unchecked")
        public E next() {
            this.checkModCount();
            return (E) SmallSet.this.container[this.index++];
        }

        /**
         * 
         * 
         */
        private void checkModCount() {
            if (this.expectedModCount != SmallSet.this.modCount) {
                throw new ConcurrentModificationException("expected: " + this.expectedModCount + " found: " + SmallSet.this.modCount);
            }
        }

        /**
         * 
         */
        public void remove() {
            this.checkModCount();
            int toRemove = this.index - 1;
            if (!SmallSet.this.checkBounds(toRemove)) {
                throw new IllegalStateException("next() has not been called yet");
            }
            if (SmallSet.this.container[toRemove] == EMPTY) {
                throw new IllegalStateException("remove() has already been called");
            }
            SmallSet.this.removeAt(toRemove);
            this.expectedModCount++;
        }
    }

    /**
     * @return int
     */
    @Override
    public int hashCode() {
        int result = this.size;
        return result;
    }

    /**
     * @param obj {@link Object}
     * @return boolean
     */
    @SuppressWarnings("unchecked")
    @Override
    public boolean equals(final Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (this.getClass() != obj.getClass()) {
            return false;
        }
        final SmallSet<E> other = (SmallSet<E>) obj;
        if (this.size != other.size) {
            return false;
        }
        return this.containsAll(other) && other.containsAll(this);
    }
}
